import java.util.*;

/**
 * 队列+宽搜
 * 103、二叉树的锯齿形层序排序
 */
public class Day15 {
     public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        // 锯齿形遍历就是当 层数是偶数的时候，将其从后往前遍历，也就是相当于正序遍历之后翻转一下
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int level = 1; // 标记为，当可以%2==0的时候就是需要进行翻转
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> tmp = new ArrayList<>();
            for(int i = 0;i < size;i++) {
                TreeNode t = queue.poll();
                tmp.add(t.val);
                if(t.left != null) {
                    queue.add(t.left);
                }
                if(t.right != null) {
                    queue.add(t.right);
                }
            }
            // 判断是否需要翻转
            if(level % 2 == 0) {
                Collections.reverse(tmp);
            }
            ret.add(tmp);
            level++;
        }
        return ret;
    }
}
